#include "bits/stdc++.h"
using namespace std;


/**
 * @brief 一个国家有 n 个城市，城市编号为 0 到 n - 1 ，题目保证 所有城市 都由双向道路 连接在一起 。道路由二维整数数组 edges 表示，其中 edges[i] = [xi, yi, timei] 表示城市 xi 和 yi 之间有一条双向道路，耗费时间为 timei 分钟。两个城市之间可能会有多条耗费时间不同的道路，但是不会有道路两头连接着同一座城市。

每次经过一个城市时，你需要付通行费。通行费用一个长度为 n 且下标从 0 开始的整数数组 passingFees 表示，其中 passingFees[j] 是你经过城市 j 需要支付的费用。

一开始，你在城市 0 ，你想要在 maxTime 分钟以内 （包含 maxTime 分钟）到达城市 n - 1 。旅行的 费用 为你经过的所有城市 通行费之和 （包括 起点和终点城市的通行费）。

给你 maxTime，edges 和 passingFees ，请你返回完成旅行的 最小费用 ，如果无法在 maxTime 分钟以内完成旅行，请你返回 -1 。
 * 
 */

// 定义比较函数
struct Compare {
    bool operator()(const std::vector<int>& a, const std::vector<int>& b) {
        // 假设我们按照第一个元素来比较vector的大小
        if (a[0] != b[0])
            return a[0] > b[0];
        else 
            return a[2] > b[2];
    }
};
class Solution {
public:
    #define P pair<int, int>
    #define INF 0x3f3f3f3f
    int minCost(int maxTime, vector<vector<int>>& edges, vector<int>& passingFees) {
        int num_citys = passingFees.size();

        // roads[i] = {j, value}, 这里表示i到j所需的时间
        vector<vector<P>> roads(num_citys, vector<P>());
        for (int i = 0; i < edges.size(); ++i) {
            roads[edges[i][0]].push_back({edges[i][1], edges[i][2]});
            roads[edges[i][1]].push_back({edges[i][0], edges[i][2]});
        }

        int fee = dijistra(maxTime, roads, passingFees);
        return fee;
    }

    // 要求距离最小的情况下，并且费用花费是最少的
    int dijistra(int maxTime, vector<vector<P>>& roads, vector<int>& passingFees) {
        // from city 0 to city n - 1
        int num_citys = passingFees.size();

        // 初始化到达每个城市的距离
        vector<int> dist(num_citys, INF);
        // 初始化到达每个城市的费用
        vector<int> fees(num_citys, INF);

        dist[0] = 0;
        fees[0] = passingFees[0];

        // 堆优化
        priority_queue<vector<int>, vector<vector<int>>, Compare> pq;
        
        pq.push({passingFees[0], 0, 0}); // fee, city_i, dis, 

        int res = INF;

        while (!pq.empty()) {
            auto ctx = pq.top();
            pq.pop();
            int cur = ctx[1];
            int dis = ctx[2];
            int fee = ctx[0];

            if (cur == num_citys - 1 && dis <= maxTime) {
                return fee;
            }

            for (int i = 0; i < roads[cur].size(); ++i) {
                P p = roads[cur][i];
                int next = p.first;
                int next_dis = p.second;
                pq.push({fee + passingFees[next], next, dis + next_dis});
            }
        }

        return -1;
    }
};